首页 > 试题广场 >

表达式求值

[编程题]表达式求值
  • 热度指数：82300 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请写一个整数计算器，支持加减乘三种运算和括号。

数据范围：，保证计算结果始终在整型范围内

要求：空间复杂度： ，时间复杂度
示例1

输入

"1+2"

输出

3
示例2

输入

"(2*(3-4))*5"

输出

-10
示例3

输入

"3+2*3*4-1"

输出

26
算法知识视频讲解
添加回答
JavaScript Node
牛客710667568号头像 牛客710667568号
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */
function solve(s) {
    let data = new Array();
    let temp = "";
    for (let i = 0; i < s.length; i++) {
        if (/[0-9]/.test(s[i])) {
            temp += s[i];
            if(i == s.length-1 && /[0-9]/.test(s[i])) {
                data.push(temp);
            }
            // console.log(temp)
        } else if (/[^0-9]/.test(s[i]) && temp !== "") {
            data.push(temp);
            data.push(s[i]);
            temp = '';
        } else {
            data.push(s[i]);
            // console.log(s[i]);
        }

    }
    console.log(data);
    // console.log(s[0])
    let stack = [];
    let chStack = [];
    for (let i = 0; i < data.length; i++) {
        if (/[0-9]/.test(data[i])) {
            stack.push(data[i]);
        } else if (data[i] == ")") {
            let temp = 0;
            while (chStack[chStack.length - 1] !== "(") {
                switch (chStack[chStack.length - 1]) {
                    case "+":
                        temp =
                            parseInt(stack[stack.length - 2]) +
                            parseInt(stack[stack.length - 1]);
                        stack.pop();
                        stack.pop();
                        chStack.pop();
                        break;
                    case "-":
                        temp =
                            parseInt(stack[stack.length - 2]) -
                            parseInt(stack[stack.length - 1]);
                        stack.pop();
                        stack.pop();
                        chStack.pop();
                        break;
                    case "*":
                        temp =
                            parseInt(stack[stack.length - 2]) *
                            parseInt(stack[stack.length - 1]);
                        stack.pop();
                        stack.pop();
                        chStack.pop();
                        break;
                    case "/":
                        temp =
                            parseInt(stack[stack.length - 2]) /
                            parseInt(stack[stack.length - 1]);
                        stack.pop();
                        stack.pop();
                        chStack.pop();
                        break;
                }
                stack.push(temp);
            }
            chStack.pop();
        } else {
            if (
                (data[i] == "+" || data[i] == "-") &&
                (chStack[chStack.length - 1] == "*" ||
                    chStack[chStack.length - 1] == "/")
            ) {
                let temp = 0;
                switch (chStack[chStack.length - 1]) {
                    case "*":
                        temp =
                            parseInt(stack[stack.length - 2]) *
                            parseInt(stack[stack.length - 1]);
                        break;
                    case "/":
                        temp =
                            parseInt(stack[stack.length - 2]) /
                            parseInt(stack[stack.length - 1]);
                        break;
                }
                stack.pop();
                stack.pop();
                stack.push(temp);
                chStack.pop();
                chStack.push(data[i]);
            } else {
                chStack.push(data[i]);
            }
        }
    }
    if (stack.length == 1) {
        console.log("jjj")
        return stack[0];
    } else {
        let temp = parseInt(stack[0]);
        stack.shift();
        while (chStack.length) {
           
            switch (chStack[0]) {
                case "+":
                    temp = temp + parseInt(stack[0])
                    stack.shift();
                    chStack.shift();
                    break;
                case "-":
                    temp = temp - parseInt(stack[0])
                    stack.shift();
                    chStack.shift();
                    break;
                case "*":
                    temp = temp * parseInt(stack[0])
                    stack.shift();
                    chStack.shift();
                    break;
                case "/":
                    temp = temp / parseInt(stack[0])
                    stack.shift();
                    chStack.shift();
                    break;
            }
        }
        return temp;
    }
    // write code here
}
module.exports = {
    solve: solve,
};

发表于 2023-09-07 12:13:31 回复(0)
JavaScript Node
果冻~头像 果冻~ 
// 第一种方法
function solve( s ){
    let stack = [],i = 0,sign='+',num=0; 
    while(i < s.length){
        if(s[i]=='('){
            let flag= 1, start = i+1;
            while(flag>0){
                i++;
                if(s[i]==')') flag--;
                if(s[i]=='(') flag++;
            }
            num = solve(s.slice(start,i));
            i--;
        }else if(s[i]>='0'&&s[i]<='9'){
            num = num*10 + Number(s[i]);
        }
        if((s[i]<'0'|| s[i]>'9') || i==s.length-1){
            if(sign=='*') stack.push(Number(stack.pop())*num);
            if(sign=='+') stack.push(Number(num));
            if(sign=='-') stack.push(Number(num)*-1);
            if(sign=='/') stack.push(Number(stack.pop())/num);
            sign = s[i];
            num = 0;
        }
        i++;
    }
    return stack.reduce((total,n)=>{return total+n},0);
}
// 第二种
function solve ( s ) {
    return eval(s);
}
// 第三种
function solve ( s ) {
    let func = new Function(`return ${s}`);
    return func();
}

发表于 2021-09-05 14:22:11 回复(6)
提交观点

问题信息

栈 递归
难度：
2条回答 6391浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号